/*
 * @lc app=leetcode.cn id=33 lang=javascript
 *
 * [33] 搜索旋转排序数组
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    // let low = 0
    // let high = nums.length - 1
    // while (low <= high) {
    //     let mid = low + ((high - low) >> 1)
    //     if (nums[mid] === target) return mid

    //     if (nums[mid] >= nums[high]) {
    //         if (nums[low] <= target && target < nums[mid]) {
    //             high = mid - 1
    //         } else {
    //             low = mid + 1
    //         }
    //     } else {
    //         if (nums[mid] < target && target <= nums[high]) {
    //             low = mid + 1
    //         } else {
    //             high = mid - 1
    //         }
    //     }
    // }
    // return -1


    let low = 0
    let high = nums.length - 1
    while (low <= high) {
        const mid = Math.floor((low + high) / 2)

        if (nums[mid] === target) return mid

        // mid 在左边有序
        if (nums[mid] >= nums[low]) {
            if (nums[low] <= target && target < nums[mid]) {
                high = mid - 1
            } else {
                low = mid + 1
            }
        } else { // mid 在右边有序
            if (nums[mid] <= target && target < nums[high]) {
                low = mid + 1
            } else {
                high = mid - 1
            }
        }
    }
    return -1
};
// @lc code=end

